1. Field of the Invention
This invention relates to cryptography and, more particularly, to a system for protecting stored and transmitted data from cryptanalytic attack.
2. Description of the Prior Art
The use of various cryptographic systems for converting secret or sensitive information from an intelligible form to an unintelligible form is well established. The intelligible form of the information or data is called "plaintext" and the unintelligible form is called "ciphertext". The process of converting from plaintext to ciphertext is called "encryption" or "encipherment" and the reverse process is called "decryption" or "decipherment". Most cryptographic systems make use of a secret value called the key. Encryption and decryption are easy when the algorithm and the key are known, but decryption should be virtually impossible without the use of the correct key. The process of attempting to find a shortcut method, not envisioned by the designer of the algorithm, for decrypting the ciphertext when the key is unknown is called "cryptanalysis".
Cryptography has a long history, tracing its roots back to at least the time of Julius Caesar who employed a substitution cipher in which each letter in the plaintext was replaced by the third later letter in the alphabet. Thus, Julius Caesar employed a linear substitution cipher which used the number three as the secret key. Non-linear substitutions, in which the alphabet is scrambled or mixed are also well-known. However, simple substitutions, whether linear or nonlinear, are relatively easy to attack when only a few sentences of the ciphertext are known. Indeed, William Legrand in Edgar Allan Poe's short story "The Gold-Bug" was able to locate a fortune in buried gold and jewels by a cryptanalytic attack on Captain Kidd's message.
Today's businesses require a much more sophisticated and secure encryption system to protect private message transmissions from computers, facsimile machines, banking machines, and the like. The most secure key based system in the history of cryptography is the one time tape or one time pad. In this system, the key is as long as the message to be encrypted and is simply added (modular arithmetic) to the message. The key is used only once and is randomly derived. Although this method is secure, it is inefficient to create new keys for every block of information transmitted and then secretly distribute these keys. Therefore, the one time tape is seldom if ever used in most applications.
The goal of modern cryptography is to create an encryption system which may not be compromised through current cryptanalytic techniques, or the benefit of breaking the system is not worth the effort required to penetrate the system. In other words, the goal is to design a system which is very difficult to break with current cryptanalytic methods. This is in contrast to the one time pad technique which is impenetrable in both theory and in practice. The one time tape should remain cryptographically unbreakable despite advances in the art of cryptanalysis. However, other prior art systems can and will be broken in time.
Modern encryption systems generally use a short key, such as a key which is eight characters in length. A good example of a modern system is the Data Encryption Standard ("DES") which was developed by IBM in the early 1970's and which was adopted by the United States Bureau of Standards as the standard encryption system for directed to the DES include U.S. Pat. Nos. 3,958,081 and 3,962,539. The Data Encryption Standard is a block type of cipher in which a portion or block of the data to be encrypted is permutated with a prearranged permutation table, modified with a key, and then substituted with a predetermined substitution table. This process is repeated numerous times in what are referred to as rounds. Permutation is also referred to as "transposition" and is a common cryptographic function in which the positions of letters in a message are scrambled in accordance with a predetermined set of directions.
Other modern encryption systems have attempted to simulate the key generation process of a one time pad by using pseudo-random generators which creates a long series of keys having the statistical property of randomness. Patents on such systems include U.S. Pat. Nos. 3,700,806 and 4,369,332. The receiver on the other end of the transmission would have a pseudo-random generator generating keys and using them to decrypt the transmitted ciphertext. Thus the system can change keys as often as desired, even changing the key for every block to be encrypted. The use of pseudo-random generators has greatly enhanced the strength of many systems, but it does not perfectly create a one time pad.
In the cryptanalysis of non-military encryption systems, the following assumptions are generally made: (1) The cryptanalyst knows the encryption system and tables used. If a pseudo-random generator is used, it is also assumed to be known. (2) The cryptanalyst does not know the key. Items 1 and 2 together are generally referred to as Kerckhoff's assumption. (3) The cryptanalyst has a large quantity of previously transmitted plaintext. (4) The cryptanalyst has a large quantity of previously recovered ciphertext corresponding to the plaintext.
A cryptographic system must demonstrate adequate strength under the above conditions. A pseudo-random generator system does not meet all of the criteria for a one time tape. If a pseudo-random generator is used, the relationship between the keys generated would then be given. Although the cryptanalyst may not know the string of keys output (if the generator were key based), he or she would still know the relationship of the key series as it is stated in the pseudo-random generator algorithm. In addition, pseudo-random generators must also be provided with a "seed" value. This, in essence, is another key which has to be generated and distributed for the system. The Data Encryption Standard, with its predetermined permutation and substitution tables and predetermined ordering of the use of these tables, is also subject to cryptanalytic attack. Although the Data Encryption Standard algorithm is a strong encryption system because it is quite complex, it is not impervious to attack by mathematical analysis.
Another technique employing some of the features of a one time pad uses a key table. In this technique, a table including numerous, predetermined keys is included in the encryption system. The keys are then each changed by the secret key. One example of this method can be seen in U.S. Pat. No. 4,776,011. This technique does not perfectly simulate the one time pad for the same reasons the pseudo-random generators do not. The original key table gives the relationship of the keys. Also, in such systems, the order in which the keys are chosen is stated by the system's algorithm, the key combinations selected may be repeated, and without an initializing vector, the same key table will always be used until a new secret key is provided. The invention disclosed herein uses a key table in a unique methodology to overcome these obstacles.
Another method for creating a strong theoretical and practical encryption system is to use a one time function. In this method, every data block encrypted is enciphered by a different cryptographic function combination. In other words, the tables used in the encryption process are variable and a different combination will be chosen by each data block.
Variable functions have also been done in prior art. One example is in U.S. Pat. No. 4,751,733 which includes the use of variable substitution. This patent has many limitations: the patent provides encryption specifically for binary words; the substitution tables must be set up and operate in close relationship to the binary arrangement of the secret key; control codes, which form a key complement or auxiliary key, are needed to direct the substitution process; the method is specifically a substitution-permutation enciphering device; the method does not provide for a variable permutation or other functions; and the method does not provide for an initializing vector which is necessary for one time tape simulation.
It is, therefore, an object of this invention to overcome the weaknesses found in other systems and produce a system which simulates the one time pad process yet requires only a single key. It is another object of the present invention to provide an encryption system which cannot be compromised in theory or in practice, and which allows for a perfect simulation of a one time pad system. It is also an object to create a cryptographic system which provides a one time method approach in that every unique block of data is functionally transformed uniquely. Such has not been accomplished by the prior art and, as a result, the system would offer stronger cryptographic measures against attack. It is also an object of the present invention to provide a secure encryption system which is flexible enough for a variety of applications, such as file storage, data transmission, telecommunication coding and the like. It is also an object to provide an encryption system which permits the use of the block cipher format and provides complete inter-symbol dependency therein.